#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>

void InsertSort(int* arr, int sz)
{
	for(int i = 0;i < sz - 1;i ++)
	{
		int tmp = arr[i + 1];
		int end = i;
		while (end >= 0)
		{
			if (arr[end] > tmp) arr[end + 1] = arr[end], end--;
			else break;
		}

		arr[end + 1] = tmp;
	}
}
void Shell(int* arr, int sz)
{
	int gap = sz;
	
	while (gap > 1)
	{

		gap = gap / 3 + 1;
		for (int i = 0; i < sz - gap; i++)
		{
			int tmp = arr[i + gap];
			int end = i;
			while (end >= 0)
			{
				if (tmp < arr[end]) arr[end + gap] = arr[end], end -= gap;
				else break;
			}

			arr[end + gap] = tmp;
		}
	}
}
int main()
{
	int arr[] = { 4, 5, 2, 6, 34, 3,7, 0, 12 };
	int len = sizeof(arr) / sizeof(int);
	Shell(arr, len);
	for (int i = 0; i < len; i++)
		printf("%d ", arr[i]);
	puts("");

	return 0;
}